package com.linyaonan.leetcode.easy._581;

import java.util.Arrays;

/**
 *
 * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 *
 * 你找到的子数组应是最短的，请输出它的长度。
 *
 * 示例 1:
 *
 * 输入: [2, 6, 4, 8, 10, 9, 15]
 * 输出: 5
 * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * 说明 :
 *
 * 输入的数组长度范围在 [1, 10,000]。
 * 输入的数组可能包含重复元素 ，所以升序的意思是<=。
 *
 *
 * @author: Lin
 * @date: 2020/1/3
 */
public class ShortestUnsorted {

    public int findUnsortedSubarray(int[] nums) {
        int[] newNums = Arrays.copyOfRange(nums, 0, nums.length);
        Arrays.sort(nums);
        int count = 0;
        // 从头统计
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == newNums[i]) {
                count++;
            } else {
                break;
            }
        }
        // 全部一致
        if (count == nums.length) {
            return 0;
        }
        // 从尾统计
        int endIndex = Math.max(nums.length - count, 0);
        for (int i = nums.length - 1; i >= 0 && endIndex >=0; i--) {
            endIndex--;
            if (nums[i] == newNums[i]) {
                count++;
            } else {
                break;
            }
        }
        return nums.length - count;
    }
}
